package com.zh.note.leetcode.greedy;

import java.util.Arrays;

/**
 * 452. 用最少数量的箭引爆气球
 */
public class LC_452_findMinArrowShots {

    // public int findMinArrowShots(int[][] points) {
    //     if (points == null || points.length == 0) {
    //         return 0;
    //     }
    //     //对数组第一个元素进行排序,从小到大
    //     Arrays.sort(points, new Comparator<int[]>() {
    //         @Override
    //         public int compare(int[] o1, int[] o2) {
    //             return Integer.compare(o1[0], o2[0]);
    //         }
    //     });
    //     int res = 1;
    //     for (int i = 1; i < points.length; i++) {
    //         if (points[i][0] > points[i - 1][0]) {
    //             res++;
    //         } else {
    //             points[i][1] = Math.min(points[i - 1][1], points[i][1]);
    //         }
    //     }
    //     return res;
    //
    // }
        public int findMinArrowShots(int[][] points) {
            if (points == null || points.length == 0) {
                return 0;
            }
            //对数组第一个元素进行排序,从小到大
            Arrays.sort(points, (o1, o2) -> Integer.compare(o1[0], o2[0]));
            int res = 1;
            for (int i = 1; i < points.length; i++) {
                // 当前气球左边界大于上一个气球右边界
                if (points[i][0] > points[i - 1][1]) {
                    res++;
                } else {
                    points[i][1] = Math.min(points[i - 1][1], points[i][1]); // 更新重叠气球最小右边界
                }
            }
            return res;
        }
}
